package com.example.algorithm.huawei_rongyao_29;

import java.util.Arrays;
import java.util.Scanner;

// 数组排序之后相邻数的最大差值

/**
 * 给定一个整形数组arr，返回排序后相邻两数的最大差值
 * arr = [9, 3, 1, 10]。如果排序，结果为[1, 3, 9, 10]，9和3的差为最大差值，故返回6。
 * arr = [5, 5, 5, 5]。返回0。
 * [要求]
 * 时间复杂度为o(n),空间复杂度为o(n)
 * 备注:
 * 1<=N<=10的6次方
 * <p>
 * 示例1
 * 输入
 * [9, 3, 1 ,10 ]
 * 输出
 * 6
 * <p>
 * 示例2
 * 输入
 * [ 5,5, 5,5]
 * 输出
 * 0
 * <p>
 * 以下程序实际测试可出正确结果。
 */
public class Q26_MaxAdjacentDifference {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        // 单参数形式：substring(int beginIndex)，从 beginIndex 开始截取到字符串的末尾。
        //双参数形式：substring(int beginIndex, int endIndex)，从 beginIndex 开始截取到 endIndex 之前（不包括 endIndex）的位置。
        String[] strs = line.substring(1, line.length() - 1).split(",");
        int n = strs.length;
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(strs[i].trim());
        }
        System.out.println("Maximum gap in arr1: " + maximumGap(numbers));
    }

    public static int maximumGap(int[] arr) {

        // arr长度是1的话就没有相邻两项比较的概念了。那就直接返回0
        if (arr == null || arr.length < 2) {
            return 0;
        }

        // Step 1: Sort the array。是题目要求排序后的...所以要拍序
        Arrays.sort(arr);

        // Step 2: Initialize maxGap to 0。打擂台时的擂台
        int maxGap = 0;

        // Step 3: Traverse the sorted array and find the maximum adjacent difference
        // 相邻两项两两比较。这个和沃尔玛面试那题有异曲同工之妙啊。
        // 首先：它是从i=1开始遍历的。
        // 其次：i < arr.length，表示i最大等于arr.length-1，也就i可以走到数组最后一个
        // 第三：它是arr[i]与arr[i - 1]比较，而不是arr[i]与arr[i+1]比较。实际写过这个算法的人知道，这个细节很重要，这个细节是与i从0开始还是i从1开始是有关联关系的。当前项与前一项比较有些时候可以防止出现索引越界。
        for (int i = 1; i < arr.length; i++) {
            int gap = arr[i] - arr[i - 1];
            if (gap > maxGap) {
                maxGap = gap;
            }
        }
        return maxGap;
    }
}

